﻿using System;
using System.Collections.Generic;

using TracedReality.Primitive;
using TracedReality.RayTracing;

namespace TracedReality.SpatialTrees
{
    /// <summary>
    /// A kd-tree implementation of a ShapeTree.
    /// </summary>
    public class ShapeKDTree : ShapeTree
    {
        /// <summary>
        /// The left child of this node.
        /// </summary>
        private ShapeKDTree left;

        /// <summary>
        /// The right child of this node.
        /// </summary>
        private ShapeKDTree right;

        /// <summary>
        /// Create a node with the given BoundingBox and depth.
        /// </summary>
        /// <param name="bb">BoundingBox that this node will contain.</param>
        /// <param name="dep">Depth of this node.</param>
        public ShapeKDTree(BoundingBox bb, int dep = 0)
        {
            bound = bb;
            depth = dep;
            shapes = new List<Shape>();
            left = null;
            right = null;
        }

        public override List<Shape> getAllShapes()
        {
            List<Shape> ashapes = new List<Shape>();
            ashapes.AddRange(shapes);
            if (left != null) { ashapes.AddRange(left.getAllShapes()); }
            if (right != null) { ashapes.AddRange(right.getAllShapes()); }

            return ashapes;
        }

        /// <summary>
        /// Check if this is a leaf node.
        /// </summary>
        /// <returns>True if this is a leaf node, false otherwise.</returns>
        public override bool isLeaf() { return left == null; }

        /// <summary>
        /// Get a count of how many Shapes are in this tree.
        /// </summary>
        /// <returns>How many Shapes are held in this tree.</returns>
        public override int getCount()
        {
            int res = shapes.Count;

            if (isLeaf()) { return res; }

            return res + left.getCount() + right.getCount();
        }

        /// <summary>
        /// Get the height of this tree.
        /// </summary>
        /// <returns>The height of the tree.</returns>
        public override int getHeight()
        {
            if (isLeaf()) { return 1; }

            return 1 + Math.Max(left.getHeight(), right.getHeight());
        }

        /// <summary>
        /// Add a Shape to this tree.
        /// </summary>
        /// <param name="s">Shape to add.</param>
        public override void add(Shape s)
        {
            if (!bound.overlaps(s.bound)) { return; }
            if (isLeaf()) { shapes.Add(s); return; }

            if (left.overlaps(s.bound) && right.overlaps(s.bound))
            {
                shapes.Add(s);
                return;
            }

            left.add(s);
            right.add(s);
        }

        /// <summary>
        /// Use this tree to check of a Ray intersects anything before a given point.
        /// </summary>
        /// <param name="ray">Ray to cast</param>
        /// <param name="t">Distance to check against.</param>
        /// <returns>True if the Ray intersects something earlier, false otherwise.</returns>
        public override bool intersectAnythingBefore(Ray ray, double t)
        {
            Hit h = new Hit();
            h.t = t;
            if (!bound.intersects(ray, h)) { return false; }

            foreach (Shape s in shapes)
            {
                if (s.Intersect(ray, h) != 0)
                {
                    if (h.t < t) { return true; }
                }
            }

            if (isLeaf()) { return false; }

            return left.intersectAnythingBefore(ray, t) || right.intersectAnythingBefore(ray, t);
        }

        /// <summary>
        /// Use this tree to cast a Ray and update a Hit.
        /// </summary>
        /// <param name="ray">Ray to cast.</param>
        /// <param name="hit">Hit to hold intersection information.</param>
        /// <returns>1 if the Ray intersects a Shape from the outside,
        /// -1 if the Ray intersects a Shape from the inside,
        /// and 0 if no intersection occurs.</returns>
        public override int castRay(Ray ray, Hit hit)
        {
            if (!bound.intersects(ray, hit)) { return 0; }

            int answer = 0;
            foreach (Shape s in shapes)
            {
                switch (s.Intersect(ray, hit))
                {
                    case 0 :
                        break;
                    case 1 :
                        answer = 1;
                        break;
                    case -1 :
                        answer = -1;
                        break;
                }
            }

            if (isLeaf()) { return answer; }

            int l = left.castRay(ray, hit);
            if (l != 0) { answer = l; }

            int r = right.castRay(ray, hit);
            if (r != 0) { answer = r; }

            return answer;
        }

        /// <summary>
        /// Split the current node if it is a leaf so that is contains no more than
        /// a given amount as long as it is above a given depth.
        /// </summary>
        /// <param name="maxcap">The maximum capacity of a node.</param>
        /// <param name="maxdep">The maximum depth of a node.</param>
        public override void split(int maxcap, int maxdep)
        {
            if (!isLeaf())
            {
                left.split(maxcap, maxdep);
                right.split(maxcap, maxdep);
                return;
            }

            if (depth > maxdep) { return; }
            if (shapes.Count < maxcap) { return; }

            Vector diff = bound.max - bound.min;
            Vector lmin = new Vector(bound.min);
            Vector rmin = new Vector(bound.min);
            Vector lmax = new Vector(bound.max);
            Vector rmax = new Vector(bound.max);

            if (diff.x >= diff.y && diff.x >= diff.z)
            {
                diff = new Vector(diff.x / 2.0, 0, 0);
            }
            else if (diff.y >= diff.x && diff.y >= diff.z)
            {
                diff = new Vector(0, diff.y / 2.0, 0);
            }
            else
            {
                diff = new Vector(0, 0, diff.z / 2.0);
            }

            rmin += diff;
            lmax -= diff;

            left = new ShapeKDTree(new BoundingBox(lmin, lmax), depth + 1);
            right = new ShapeKDTree(new BoundingBox(rmin, rmax), depth + 1);

            List<Shape> oldlist = new List<Shape>(shapes);
            shapes = new List<Shape>();
            foreach (Shape s in oldlist) { add(s); }

            left.split(maxcap, maxdep);
            right.split(maxcap, maxdep);
        }

        public override void shrink()
        {
            List<BoundingBox> bbs = new List<BoundingBox>();
            if (!isLeaf())
            {
                left.shrink();
                bbs.Add(left.bound);

                right.shrink();
                bbs.Add(right.bound);
            }

            foreach (Shape s in shapes) { bbs.Add(s.bound); }

            Vector center = bound.center;
            bound = BoundingBox.Minimum(bbs);

            if (bbs.Count == 0) { bound.translate(center); }
        }
    }
}
